
package com.huawei.common.okhttp;

import java.util.Arrays;
import java.util.Random;

/**
 * 功能描述
 *
 * @author cWX1142527
 * @since 2023年01月18日
 */
public class Java_327_区间和 {
    public static void main(String args[]) {
        Random random = new Random();
        int n = 20;
        for (int i = 0; i < n; i++) {
            // length = [1 - n]
            int length = random.nextInt(n) + 1;
            int[] nums = new int[length];
            for (int j = 0; j < length; j++) {
                nums[j] = random.nextInt(n);
            }
            int lower = random.nextInt() - 5;
            int upper = random.nextInt() + 20;
            System.out.println("区间和个数：" + countRangeSum(nums, lower, upper));
            System.out.println("对拍区间和个数：" + duiPai(nums, lower, upper));
        }
        /*
         * int[] nums = new int[]{-2, 5, -1, 1, -1};
         * int lower = -2;
         * int upper = 2;
         * System.out.println("对拍区间和个数：" + duiPai(nums, lower, upper));
         * System.out.println("区间和个数：" + countRangeSum(nums, lower, upper));
         */
    }

    public static int duiPai(int[] nums, int lower, int upper) {
        // 暴力算法： 遍历所有区间获取其和的值。 sum(i ) = sum(i - 1) + nums[i] ... ; 复杂度 n + (n-1）+ (n
        // -2) ... + 1 = （n + 1）*n/2 O(n2)
        int[] sumNums = new int[nums.length];

        int cout = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                sumNums[i] = nums[i];
            } else {
                sumNums[i] = sumNums[i - 1] + nums[i];
            }
            if (sumNums[i] <= upper && sumNums[i] >= lower) {
                cout++;
            }
        }

        for (int i = 0; i < sumNums.length; i++) {
            for (int j = i + 1; j < sumNums.length; j++) {
                if (sumNums[j] - sumNums[i] <= upper && sumNums[j] - sumNums[i] >= lower) {
                    cout++;
                }
            }
        }
        return cout;
    }

    /**
     * 分治-合并算法实现
     * 
     * @param nums
     * @param lower
     * @param upper
     * @return
     */
    public static int countRangeSum(int[] nums, int lower, int upper) {
        // 分治算法： 遍历所有区间获取其和的值。 sum(i + 1) = sum(i) + nums[i] ... ;
        // 第一个sum(right) - sum(left) >= lower 那么right 后面的值都满足 >= lower这个条件， 第一个满足这个条件的
        // 下标记录为i,
        // 后续 sum(right) - sum(left) <=upper 一个不满足，后续都不满足，第一个不满足这个条件的下标记录 j 那么满足的个数是
        // count = j - i
        // 计算sum(right) - sum(left + 1) >= lower 因为数组递增的，所以 右侧的从上次 第一个满足条件的i 开始计算满足，
        // 下面流程一样，
        // 左右两个数组全部计算完后，进行合并排序，然后在继续上速步骤
        int[] sumNums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                sumNums[i] = nums[i];
            } else {
                sumNums[i] = sumNums[i - 1] + nums[i];
            }
        }
        int[] count = new int[]{0};
        mergeAndCountRangeSum(sumNums, lower, upper, count);
        return count[0];
    }

    public static int[] mergeAndCountRangeSum(int[] nums, int lower, int upper, int[] count) {
        if (nums.length == 1) {
            count[0] = (nums[0] <= upper && nums[0] >= lower) ? count[0] + 1 : count[0];
            return nums;
        }

        int mid = nums.length / 2;
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid, nums.length);
        int[] mergeLeft = mergeAndCountRangeSum(left, lower, upper, count);
        int[] mergeRigth = mergeAndCountRangeSum(right, lower, upper, count);

        int startIndex = 0;
        for (int i = 0; i < mergeLeft.length; i++) {
            boolean lowerStartIndex = false;
            for (int j = startIndex; j < mergeRigth.length; j++) {
                // 大于 upper时
                if (mergeRigth[j] - mergeLeft[i] > upper) {
                    break;
                }

                // 小于 lower时
                if (mergeRigth[j] - mergeLeft[i] < lower) {
                    continue;
                }

                if (mergeRigth[j] - mergeLeft[i] >= lower && !lowerStartIndex) {
                    startIndex = j;
                    lowerStartIndex = true;
                }
                if (mergeRigth[j] - mergeLeft[i] >= lower && mergeRigth[j] - mergeLeft[i] <= upper) {
                    count[0] += 1;
                }
            }
        }

        return merge(nums, mergeLeft, mergeRigth);
    }

    public static int[] merge(int[] nums, int[] left, int[] right) {
        int r = 0;
        int l = 0;
        for (int i = 0; i < nums.length; i++) {
            if (l >= left.length) {
                nums[i] = right[r++];
            } else if (r >= right.length) {
                nums[i] = left[l++];
            } else if (right[r] >= left[l]) {
                nums[i] = left[l++];
            } else {
                nums[i] = right[r++];
            }
        }
        return nums;
    }
}
